package leetcode

/*
 * @lc app=leetcode.cn id=605 lang=golang
 *
 * [605] 种花问题
 */

// @lc code=start
func canPlaceFlowers1(flowerbed []int, n int) bool {
	flowerbed = append([]int{0}, flowerbed...)
	flowerbed = append(flowerbed, 0)
	for i := 1; i < len(flowerbed)-1 && n > 0; i++ {
		if flowerbed[i-1] == 0 && flowerbed[i] == 0 && flowerbed[i+1] == 0 {
			flowerbed[i] = 1
			n--
		}
	}
	if n > 0 {
		return false
	}
	return true
}

func canPlaceFlowers2(flowerbed []int, n int) bool {
	flowerbed = append([]int{0}, flowerbed...)
	flowerbed = append(flowerbed, 0)
	for i := 1; i < len(flowerbed)-1 && n > 0; i++ {
		if flowerbed[i-1] == 0 && flowerbed[i] == 0 && flowerbed[i+1] == 0 {
			flowerbed[i] = 1
			n--
			i++
		}
	}
	if n > 0 {
		return false
	}
	return true
}

func canPlaceFlowers3(flowerbed []int, n int) bool {
	if n == 0 {
		return true
	}
	l := len(flowerbed)
	if l == 1 {
		if flowerbed[0] == 0 && n == 1 {
			return true
		}
		return false
	}
	for i := 0; i < l && n > 0; i++ {
		if i == 0 {
			if flowerbed[i] == 0 && flowerbed[i+1] == 0 {
				flowerbed[i] = 1
				n--
				i++
			}
		} else if i == l-1 {
			if flowerbed[i-1] == 0 && flowerbed[i] == 0 {
				n--
			}
		} else {
			if flowerbed[i-1] == 0 && flowerbed[i] == 0 && flowerbed[i+1] == 0 {
				flowerbed[i] = 1
				n--
				i++
			}
		}
	}
	if n > 0 {
		return false
	}
	return true
}

// 参考最优时间
func canPlaceFlowers(flowerbed []int, n int) bool {
	l := len(flowerbed)
	for i := 0; i < l; i += 2 {
		if flowerbed[i] == 0 {
			if i+1 == l || flowerbed[i+1] == 0 {
				n--
			} else {
				i++
			}
		}
		if n <= 0 {
			return true
		}
	}
	return false
}

// 以下参考官方答案
func canPlaceFlowers4(flowerbed []int, n int) bool {
	prev := -2
	l := len(flowerbed)
	for i := 0; i < l && n > 0; i++ {
		if flowerbed[i] == 1 {
			n -= (i - prev - 2) / 2
			prev = i
		}
	}
	n -= (l - prev - 1) / 2
	if n > 0 {
		return false
	}
	return true
}

func canPlaceFlowers5(flowerbed []int, n int) bool {
	prev := -2
	l := len(flowerbed)
	for i := 0; i < l; i++ {
		if flowerbed[i] == 1 {
			n -= (i - prev - 2) / 2
			if n <= 0 {
				return true
			}
			prev = i
		}
	}
	n -= (l - prev - 1) / 2
	if n > 0 {
		return false
	}
	return true
}

// @lc code=end
